/*
 * (C) Copyright 2014-2018, by Dimitrios Michail
 *
 * JHeaps Library
 * 
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.jheaps.monotone

import org.jheaps.AddressableHeap
import org.jheaps.annotations.ConstantTime
import org.jheaps.annotations.LogarithmicTime
import java.io.Serializable
import kotlin.math.min

/**
 * Base abstract implementation of an addressable radix heap.
 *
 * @author Dimitrios Michail
 *
 * @param <K>
 * the type of keys maintained by this heap
 * @param <V>
 * the type of values maintained by this heap
</V></K> */
abstract class AbstractRadixAddressableHeap<K, V>() : AddressableHeap<K, V>, Serializable {
    /**
     * The buckets as lists.
     */
    protected lateinit var buckets: Array<Node?>

    /**
     * Number of elements
     */
    protected var size: Long = 0

    /**
     * Last deleted key. This value is used to distribute elements in the
     * buckets. Should be initialized with the [.minKey] value.
     */
    protected var lastDeletedKey: K? = null

    /**
     * The current minimum value (cached)
     */
    protected var currentMin: Node? = null

    /**
     * Minimum key allowed
     */
    protected var minKey: K? = null

    /**
     * Maximum key allowed
     */
    protected var maxKey: K? = null

    /**
     * {@inheritDoc}
     */
    @ConstantTime
    override fun findMin(): Node {
        if (size == 0L) {
            throw NoSuchElementException()
        }
        return currentMin!!
    }

    /**
     * {@inheritDoc}
     *
     * @throws IllegalArgumentException
     * if the key is null
     * @throws IllegalArgumentException
     * if the key is less than the minimum allowed key
     * @throws IllegalArgumentException
     * if the key is more than the maximum allowed key
     * @throws IllegalArgumentException
     * if the key is less than the last deleted key (or the minimum
     * key allowed if no key has been deleted)
     */
    @ConstantTime
    override fun insert(key: K): Node {
        return insert(key, null)
    }

    /**
     * {@inheritDoc}
     *
     * @throws IllegalArgumentException
     * if the key is null
     * @throws IllegalArgumentException
     * if the key is less than the minimum allowed key
     * @throws IllegalArgumentException
     * if the key is more than the maximum allowed key
     * @throws IllegalArgumentException
     * if the key is less than the last deleted key (or the minimum
     * key allowed if no key has been deleted)
     */
    @ConstantTime
    override fun insert(key: K, value: V?): Node {
        if (key == null) {
            throw IllegalArgumentException("Null keys not permitted")
        }
        if (compare(key, maxKey) > 0) {
            throw IllegalArgumentException("Key is more than the maximum allowed key")
        }
        if (compare(key, lastDeletedKey) < 0) {
            throw IllegalArgumentException("Invalid key. Monotone heap.")
        }

        // add to bucket
        val p = Node(key, value)
        val b: Int = computeBucket(key, lastDeletedKey)
        p.bucket = b
        if (buckets[b] == null) {
            buckets[b] = p
        } else {
            buckets[b]!!.prev = p
            p.next = buckets[b]
            buckets[b] = p
        }

        // update current minimum cache
        if (currentMin == null || compare(key, currentMin!!.key) < 0) {
            currentMin = p
        }

        size++
        return p
    }

    /**
     * {@inheritDoc}
     *
     * The cost of this operation is amortized O(logC) assuming the heap
     * contains keys in the range [0, C] or equivalently [a, a+C].
     */
    @LogarithmicTime(amortized = true)
    override fun deleteMin(): Node {
        if (size == 0L) {
            throw NoSuchElementException()
        }

        
        // updated last deleted key
        val result: Node = currentMin!!
        lastDeletedKey = currentMin!!.key

        if (currentMin!!.bucket == 0) {
            val head = buckets[currentMin!!.bucket]
            if (currentMin!!.next != null) {
                currentMin!!.next!!.prev = currentMin!!.prev
            }
            if (currentMin!!.prev != null) {
                currentMin!!.prev!!.next = currentMin!!.next
            }
            if (head === currentMin) {
                currentMin!!.prev = null
                buckets[currentMin!!.bucket]= currentMin!!.next
            }
            currentMin!!.next = null
            currentMin!!.prev = null
            currentMin!!.bucket = EMPTY

            // update minimum cache
            currentMin = buckets[0]
            if (--size > 0) {
                findAndCacheMinimum(0)
            }
        } else {
            // redistribute all elements based on new lastDeletedKey
            var newMin: Node? = null

            val currentMinBucket: Int = currentMin!!.bucket
            var `val` = buckets[currentMinBucket]
            while (`val` != null) {
                // remove first from list
                buckets[currentMinBucket] = `val`.next
                if (buckets.get(currentMinBucket) != null) {
                    buckets.get(currentMinBucket)!!.prev = null
                }
                `val`.next = null
                `val`.prev = null
                `val`.bucket = EMPTY

                // redistribute
                if (`val` !== currentMin) {
                    val b: Int = computeBucket(`val`.key, lastDeletedKey)
                    assert(b < currentMinBucket)
                    `val`.next = buckets[b]
                    if (buckets[b] != null) {
                        buckets[b]!!.prev = `val`
                    }
                    buckets[b] = `val`
                    `val`.bucket = b

                    if (newMin == null || compare(`val`.key, newMin.key) < 0) {
                        newMin = `val`
                    }
                }
                `val` = buckets.get(currentMinBucket)
            }

            // update minimum cache
            currentMin = newMin
            if (--size > 0) {
                findAndCacheMinimum(currentMinBucket + 1)
            }
        }

        return result
    }

    @get:ConstantTime
    override val isEmpty: Boolean
        get() {
            return size == 0L
        }

    /**
     * {@inheritDoc}
     */
    @ConstantTime
    override fun size(): Long {
        return size
    }

    /**
     * {@inheritDoc}
     */
    override fun clear() {
        for (i in buckets.indices) {
            buckets[i] = null
        }
        size = 0
        lastDeletedKey = minKey
        currentMin = null
    }

    /**
     * Always returns `null` since this heap uses the
     * [natural ordering][Comparable] of its keys.
     *
     * @return `null` since this heap uses the natural ordering of its
     * keys
     */
    override fun comparator(): Comparator<in K?>? {
        return null
    }

    /**
     * Compares its two arguments for order. Returns a negative integer, zero,
     * or a positive integer as the first argument is less than, equal to, or
     * greater than the second.
     *
     * @param o1
     * the first object to be compared.
     * @param o2
     * the second object to be compared.
     * @return a negative integer, zero, or a positive integer as the first
     * argument is less than, equal to, or greater than the second.
     */
    protected abstract fun compare(o1: K, o2: K?): Int

    /**
     * Compute the bucket of a key based on a minimum key.
     *
     * @param key
     * the key
     * @param minKey
     * the minimum key
     * @return the bucket where the key should go
     */
    protected fun computeBucket(key: K, minKey: K?): Int {
        return (1 + min(msd(key, minKey).toDouble(), (buckets.size - 2).toDouble())).toInt()
    }

    /**
     * Compute the most significant digit which is different in the binary
     * representation of two values, or -1 if numbers are equal.
     *
     * @param a
     * the first value
     * @param b
     * the second value
     * @return the most significant digit which is different or -1 if numbers
     * are equal
     */
    protected abstract fun msd(a: K, b: K?): Int

    /**
     * List Node
     */
    inner class Node(override var key: K, override var value: V?) : AddressableHeap.Handle<K, V>,
        Serializable {
        var next: Node? = null
        var prev: Node? = null
        var bucket: Int

        init {
            this.bucket = EMPTY
        }

        override fun decreaseKey(newKey: K) {
            if (size == 0L) {
                throw IllegalArgumentException("Invalid handle!")
            }
            if (bucket == EMPTY) {
                throw IllegalArgumentException("Invalid handle!")
            }
            if (compare(newKey, lastDeletedKey) < 0) {
                throw IllegalArgumentException("Invalid key. Monotone heap.")
            }

            val c: Int = compare(newKey, key)
            if (c > 0) {
                throw IllegalArgumentException("Keys can only be decreased!")
            }

            key = newKey
            if (c == 0) {
                return
            }

            // update minimum cache
            if (this === currentMin || compare(key, currentMin!!.key) < 0) {
                currentMin = this
            }

            // find new bucket
            val newBucket: Int = computeBucket(key, lastDeletedKey)
            if (newBucket == bucket) {
                return
            }

            // remove from list
            val head: Node? = buckets[bucket]
            if (next != null) {
                next!!.prev = prev
            }
            if (prev != null) {
                prev!!.next = next
            }
            if (head === this) {
                prev = null
                buckets[bucket] = next
            }

            // add to new list
            if (buckets[newBucket] == null) {
                buckets[newBucket] = this
                this.next = null
            } else {
                buckets[newBucket]!!.prev = this
                this.next = buckets[newBucket]
                buckets[newBucket] = this
            }
            this.prev = null
            this.bucket = newBucket
        }

        override fun delete() {
            if (size == 0L || bucket == EMPTY) {
                throw IllegalArgumentException("Invalid handle!")
            }

            if (this === currentMin) {
                deleteMin()
                return
            }

            // remove from list
            val head = buckets[bucket]
            if (next != null) {
                next!!.prev = prev
            }
            if (prev != null) {
                prev!!.next = next
            }
            if (head === this) {
                buckets[bucket] = next
            }
            prev = null
            next = null
            bucket = EMPTY
            size--
        }

    }

    /**
     * Helper method for finding and caching the minimum. Assumes that the heap
     * contains at least one element.
     *
     * @param firstBucket
     * start looking for elements from this bucket
     */
    private fun findAndCacheMinimum(firstBucket: Int) {
        if (currentMin == null) {
            // find first non-empty bucket
            var currentMinBucket: Int = EMPTY
            for (i in firstBucket until buckets.size) {
                if (buckets[i] != null) {
                    currentMinBucket = i
                    break
                }
            }
            // find new minimum and cache it
            if (currentMinBucket >= 0) {
                var `val`: Node? = buckets.get(currentMinBucket)
                while (`val` != null) {
                    if (currentMin == null || compare(`val`.key, currentMin!!.key) < 0) {
                        currentMin = `val`
                    }
                    `val` = `val`.next
                }
            }
        }
    }

    companion object {
        private val serialVersionUID: Long = 1L

        /**
         * Denotes that a key does not belong to a bucket
         */
        protected val EMPTY: Int = -1
    }
}
